package com.practice.niuke.new_direct_basics.class15;

/**
 * 换钱的方法数
 * 【题目】
 * 给定数组 arr， arr 中所有的值都为正数且不重复。 每个值代表一种面值的货币， 每种面值
 * 的货币可以使用任意张， 再给定一个整数 aim， 代表要找的钱数， 求组成 aim 有多少种方法。
 */
public class CoinsWays {

    /**
     * arr中都是正数且无重复值，返回组成aim的方法数（TODO：标记调用递归函数的主函数）
     *
     * @param arr 货币面值数组
     * @param aim 目标值
     * @return 组成aim的方法数
     */
    public static int ways(int[] arr, int aim) {
        // 洗一下无效参数
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // 调用递归函数
        return process(arr, 0, aim);
    }

    /**
     * 如果自由使用arr[index...]的面值（index位置和后续位置的面值都可以使用），
     * 要组成rest这么多钱，返回方法数。
     *
     * @param arr   货币面值数组, 固定参数
     * @param index 当前来到了index位置，考虑当前位置和后续位置的面值要还是不要
     * @param rest  还要组成rest这么多钱
     * @return int
     */
    public static int process(int[] arr, int index, int rest) {
        // 已经没有面值可选
        if (index == arr.length) {
            // 在没有面值可选的前提下，如果当前要组成的钱数是0则返回1，否则返回0；
            return rest == 0 ? 1 : 0;
        }
        // 还有面值可选
        int ways = 0;
        // arr[index]为当前面值，从0张开始尝试，使用多少张arr[index]面值的钞票。
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process(arr, index + 1, rest - zhang * arr[index]);
        }
        return ways;
    }

    /**
     * 将上面的递归改为动态规划（TODO：递归改为动态规划）
     *
     * @param arr 货币面值数组, 固定参数
     * @param aim 目标值
     * @return 组成aim的方法数
     */
    public static int waysdp(int[] arr, int aim) {
        // 洗一下无效参数
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        // base case
        dp[N][0] = 1;
        // 大顺序：从下往上
        for (int i = N - 1; i >= 0; i--) {
            // 具体一行：从左往右
            for (int rest = 0; rest <= aim; rest++) {
                dp[i][rest] = dp[i + 1][rest];
                // 左移后不越界
                if (rest - arr[i] >= 0) {
                    dp[i][rest] += dp[i][rest - arr[i]];
                }
            }
        }
        // 看主流程调用方式
        return dp[0][aim];
    }

    // for test
    public static int[] generateRandomArray(int len, int max) {
        int[] arr = new int[(int) (Math.random() * len) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max) + 1;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 3, 1};
        int sum = 350;
        System.out.println(ways(arr, sum));
        System.out.println(waysdp(arr, sum));
    }

}
